package com.yeung.swordoffer;


/**
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
 * 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 */
public class 构建乘积数组 {
    public static void main(String[] args) {

    }

    public int[] multiply(int[] A) {
        //利用上下三角的思想
        int n = A.length;
        int b[] = new int[n];
        //计算下三角, 元素i之前的连乘
        b[0] = 1;
        for (int i = 1; i < n; i++) {
            //第一个元素左边没有连乘, 从1开始
            b[i] = b[i - 1] * A[i - 1];
        }
        //计算上三角,元素i的右边的连乘
        int tmp = 1;
        for (int k = n - 2; k >= 0; k--) {//n-2, 从倒数第二个元素开始计算,倒数第一个没有右连乘
            tmp *= A[k + 1];//记录i元素的右连乘
            b[k] *= tmp;
        }
        return b;
    }
}
